<?php
//求两个自然数的最大公约数

class GreatestCommonDivisor {

    private $times;

    public function resetTimes() {
        $this->times = 0;
    }

    public function getTimes() {
        return $this->times;
    }

    private function log(string $msg) {
        //echo $msg;
    }

    /**
     * 欧几里德的辗转相除法(对大数的取模运算性能比较差)
     * @param int $a
     * @param int $b
     * @return int
     */
    public function euclidean(int $a, int $b) {
        $this->times++;
        if ($a < $b) {
            $t = $a;
            $a = $b;
            $b = $t;
        }
        $c = $a % $b;
        $this->log($this->times . ': ' . $a . ' % ' . $b . ' = ' . $c . PHP_EOL);
        if ($c == 0) {
            return $b;
        }
        return $this->euclidean($b, $c);
    }

    /**
     * 更相减损术(性能不固定, 当两个数相差较大时要递归很多次)
     * @param int $a
     * @param int $b
     * @return int
     */
    public function gengXiangJianSun(int $a, int $b) {
        $this->times++;
        if ($a < $b) {
            $t = $a;
            $a = $b;
            $b = $t;
        }
        $c = $a - $b;
        $this->log('G' . $this->times . ': ' . $a . ' - ' . $b . ' = ' . $c . PHP_EOL);
        if ($c == 0) {
            return $b;
        }
        return $this->gengXiangJianSun($b, $c);
    }

    /**
     * Stein: 辗转相除法和更相减损术结合+对偶数的移位
     * @param int $a
     * @param int $b
     * @return int
     */
    public function stein(int $a, int $b) {
        if ($a === $b) {
            return $a;
        }
        if ($a < $b) {
            $t = $a;
            $a = $b;
            $b = $t;
        }

        if (($a & 1) === 0 && ($b & 1) === 0) {
            //如果都是偶数, 则为都右移移位的gcd*2
            $this->times++;
            $this->log('A' . $this->times . ': 偶+偶 ' . PHP_EOL);
            return $this->stein($a >> 1, $b >> 1) << 1;
        }
        else if (($a & 1) === 0 && ($b & 1) !== 0) {
            //一偶数一奇数
            $this->times++;
            $this->log('A' . $this->times . ': 偶+奇 ' . PHP_EOL);
            return $this->stein($a >> 1, $b);
        }
        else if (($a & 1) !== 0 && ($b & 1) === 0) {
            //一偶数一奇数
            $this->times++;
            $this->log('A' . $this->times . ': 奇+奇 ' . PHP_EOL);
            return $this->stein($a, $b >> 1);
        }
        else {
            //都是奇数, 采用更相减损术, 得到一个偶数一个奇数
            return $this->stein($a - $b, $b);
        }
    }

}

$m = new GreatestCommonDivisor();
$a = 1256 * 9871 * 8251 * 78315;
$b = 1128 * 6782 * 3613 * 94674;
$t1 = microtime(true);
$m->resetTimes();
$rt = $m->euclidean($a, $b);
echo '辗转相除法的结果: ' . $rt . ', 运算' . $m->getTimes() . '次' . PHP_EOL;

$t2 = microtime(true);
echo '用时 ' . (round($t2 - $t1, 6) * 1000) . ' ms' . PHP_EOL;

//$m->resetTimes();
////更相减损术: 两数相差巨大时OOM
//echo '更相减损术的结果:' . $m->gengXiangJianSun($a, $b) . ', 运算' . $m->getTimes() . '次' . PHP_EOL;

$t1 = microtime(true);

$m->resetTimes();
$rt = $m->stein($a, $b);
echo 'Stein的结果:' . $rt . ', 运算' . $m->getTimes() . '次' . PHP_EOL;

$t2 = microtime(true);
echo '用时 ' . (round($t2 - $t1, 6) * 1000) . ' ms' . PHP_EOL;
